home *** CD-ROM | disk | FTP | other *** search
/ Trading on the Edge / Trading On The Edge - CD-ROM Toolkit (Wayzata Technology)(2031)(1994).bin / pc / mac_file / vendor_d / ga_softw / ooga / reusable.lis < prev    next >
File List  |  1991-02-03  |  8KB  |  232 lines
  1. ;;; -*- Mode:Lisp; Package:OOGA; Base:10; Syntax:COMMON-LISP -*-
  2. #||
  3.             RESTRICTED RIGHTS LEGEND
  4.                     
  5.  Use, duplication, or disclosure by the Government is subject to
  6.  restrictions as set forth in subdivision (b)(3)(ii) of the Rights in
  7.  Technical Data and Computer Software Clause at 52.227-7013 of the DOD
  8.  FAR Supplement.
  9.                     
  10.                 TSP (The Software Partnership)
  11.                 P.O. Box 991
  12.                 Melrose, MA 02176
  13.                     
  14.       Copyright 1990 by Lawrence Davis and Daniel Cerys, all rights reserved.
  15. ||#
  16.  
  17. (in-package :ooga)
  18.  
  19.  
  20. #|
  21.  
  22. This file contains class descriptions for four commonly-used
  23. genetic algorithms:  the traditional, binary genetic algorithm;
  24. the steady-state genetic algorithm without duplicates; a
  25. real-number genetic algorithm; and an order-based genetic
  26. algorithm.  They are available for specialization, but see the
  27. system documentation for the proper way to use them.
  28.  
  29. |#
  30.  
  31.  
  32. ;************************************************************
  33.  
  34. ;    TRADITIONAL GENETIC ALGORITHM
  35.  
  36.  
  37. ;;; Note that this GA is missing several particulars.  See the
  38. ;;; HOW-TO-EXAMPLES.LISP file for the missing particulars and
  39. ;;; how to fill them in.
  40.  
  41. ;;; The traditional GA uses linear-normalization (although there
  42. ;;; really is no standard fitness technique), roulette-wheel
  43. ;;; parent selection (although Baker's technique is probably
  44. ;;; better), binary representation (although some researchers
  45. ;;; prefer Gray coding), random initialization,
  46. ;;; generational replacement, and the one point crossover and
  47. ;;; mutate operator.  
  48.  
  49. ;;; A good deal of the research in the genetic algorithm field
  50. ;;; has involved modifications of and extensions to
  51. ;;; algorithms like this one.
  52.  
  53. (defclass TRADITIONAL-GA (basic-genetic-algorithm) ())
  54.  
  55. (def-append-method GET-PARTICULARS ((ga traditional-ga))
  56.     `((fitness-technique ,(make-instance 'linear-normalization))
  57.       (parent-selection-technique
  58.     ,(make-instance 'roulette-wheel-parent-selection))
  59.       (representation-technique
  60.     ,(make-instance 'binary-representation))
  61.       (initialization-technique
  62.     ,(make-instance 'random-binary-initialization))
  63.       (reproduction-technique
  64.     ,(make-instance 'generational-replacement))
  65.       (deletion-technique ,(make-instance 'delete-all))
  66.       (operator-selection-technique
  67.     ,(make-instance 'use-first-operator))
  68.       (operator-list
  69.     ,(list (make-instance 'one-point-crossover-and-mutate))))
  70.     )
  71.  
  72.  
  73. ;************************************************************
  74.  
  75. ;    TRADITIONAL GENETIC ALGORITHM WITH ELITISM
  76.  
  77. ;;; This is a fairly widely-used variant on the traditional
  78. ;;; GA. 
  79.  
  80. (defclass TRADITIONAL-GA-WITH-ELITISM (traditional-ga) ())
  81.  
  82. (def-append-method GET-PARTICULARS ((ga traditional-ga-with-elitism))
  83.   (append (call-next-method)
  84.       `((reproduction-technique
  85.           ,(make-instance
  86.         'generational-replacement-with-elitism)))))
  87.  
  88.  
  89. ;************************************************************
  90.  
  91. ;    STEADY STATE GA
  92.  
  93. ;;; The STEADY-STATE-GA is a basic GA using 
  94. ;;; steady-state-without-duplicates and delete-last.  It can
  95. ;;; be built on to make other more complicated GA's.  It cannot
  96. ;;; be used for runs until its unspecified slots
  97. ;;; have been filled.  See the HOW-TO-EXAMPLES.LISP file for
  98. ;;; ways to fill these slots.
  99.  
  100.  
  101. (defclass STEADY-STATE-GA (basic-genetic-algorithm) ())
  102.  
  103. (def-append-method GET-PARTICULARS ((ga steady-state-ga))
  104.     `((reproduction-technique
  105.        ,(make-instance 'steady-state-without-duplicates))
  106.       (deletion-technique ,(make-instance 'delete-last))))
  107.  
  108.  
  109. ;************************************************************
  110.  
  111. ;    ADVANCED-TECHNIQUES GENETIC ALGORITHM
  112.  
  113. ;;; The advanced-techniques genetic algorithm uses the
  114. ;;; steady-state-without-duplicates,
  115. ;;; roulette-wheel-parent-selection, linear-normalization, and
  116. ;;; roulette-wheel-operator-selection techniques
  117. ;;; introduced in the Handbook of Genetic Algorithms.
  118. ;;; It is included here so that users who wish to create
  119. ;;; algorithms using those techniques can add them simply.
  120.  
  121. (defclass ADVANCED-TECHNIQUES-GENETIC-ALGORITHM
  122.       (steady-state-ga) ())
  123.  
  124.  
  125. (defmethod GET-PARTICULARS append
  126.        ((ga advanced-techniques-genetic-algorithm))
  127.     `((parent-selection-technique
  128.     ,(make-instance 'roulette-wheel-parent-selection))
  129.       (fitness-technique ,(make-instance 'linear-normalization))
  130.       (operator-selection-technique
  131.     ,(make-instance 'roulette-wheel-operator-selection))))
  132.  
  133. ;************************************************************
  134.  
  135. ;    REAL-VALUED GENETIC ALGORITHM
  136.  
  137.  
  138. ;;; The real-valued genetic algorithm uses a chromosome
  139. ;;; consisting of a list of real numbers.  It also uses an
  140. ;;; operator list consisting of the five operators used in GA
  141. ;;; 5-1.  The parameterization of these operators can be
  142. ;;; accomplished by creating them oneself on the model of the
  143. ;;; operator list in GA 5-1.
  144.  
  145. ;;; Note that the real number mutation operator requires a spec
  146. ;;; telling it what the legal range of values for each
  147. ;;; chromosome position it.  OOGA will match up each spec in
  148. ;;; order with its corresponding chromosome position.  If OOGA
  149. ;;; runs out of specs, it will reuse the last one for each
  150. ;;; subsequent chromosome position.  This operator also requires
  151. ;;; a parameter telling it what the probability is of mutating
  152. ;;; any field.
  153.  
  154. ;;; Note that the creep operator requires a spec telling it how
  155. ;;; much to creep.  The creeping will be a number in this range,
  156. ;;; generated from a level distribution.  This operator also
  157. ;;; requires a parameter telling it what the probability s of
  158. ;;; creeping any field.  "Big creep" and "little creep"
  159. ;;; operators are made by installing higher creep probabilities
  160. ;;; and greater creep ranges in the big creep operator, and
  161. ;;; smaller ones in the little creep operator.
  162.  
  163. ;;; The list of operator weights is a fairly robust one.  You may wish
  164. ;;; to add a parameter interpolation method that varies the list
  165. ;;; over the course of the run.  If you modify the length of the
  166. ;;; operator list, you must also modify the length of the
  167. ;;; operator weight list.
  168.  
  169.  
  170. (defclass REAL-VALUE-GENETIC-ALGORITHM (basic-genetic-algorithm)
  171.     ())
  172.  
  173. (def-append-method GET-PARTICULARS ((ga real-value-genetic-algorithm))
  174.     `((representation-technique
  175.     ,(make-instance 'real-number-representation
  176.             :real-number-specs '((0 4194303 t))
  177.             :chromosome-length 2))
  178.       (initialization-technique
  179.     ,(make-instance 'random-real-number-initialization))
  180.       (operator-list
  181.     ,(list (make-instance 'uniform-list-crossover)
  182.            (make-instance 'average-crossover)
  183.            (make-instance 'real-number-mutation
  184.                   :mutation-rate .5
  185.                   :mutation-specs '((0 4194303 t)))
  186.            (make-instance 'real-number-creep
  187.                   :creep-rate .7
  188.                   :creep-specs '((70000 t)))
  189.            (make-instance 'real-number-creep
  190.                   :creep-rate .6
  191.                   :creep-specs '((2000 t)))))
  192.       (operator-weights ,(list 10 40 10 30 10))
  193.       (reproduction-parameterization-techniques
  194.     ,(list (make-instance
  195.          'interpolate-operator-weights
  196.          :interpolation-specs
  197.          '((10 40 10 30 10) (10 20 0 40 30)))))))
  198.  
  199.  
  200.  
  201. ;************************************************************
  202.  
  203. ;    ORDER-BASED GENETIC ALGORITHM
  204.  
  205. ;;; An order-based genetic algorithm uses chromosomes that are
  206. ;;; permutations of a basic list.  It also uses the
  207. ;;; scramble-sublist and uniform-order-based-crossover
  208. ;;; operators.  The weightings of these operators are those used
  209. ;;; in the example in the Handbook of Genetic Algorithms.
  210.  
  211. ;;; Note that the user should define the LIST-TO-PERMUTE method
  212. ;;; for any evaluator used with the particulars described below.
  213. ;;; The random-permutation initialization technique uses this
  214. ;;; method to fill its list-to-permute slot on initialization
  215. ;;; for a run.
  216.  
  217. (defclass ORDER-BASED-GENETIC-ALGORITHM
  218.       (basic-genetic-algorithm) ())
  219.  
  220.  
  221. (def-append-method GET-PARTICULARS ((ga order-based-genetic-algorithm))
  222.     `((representation-technique ,(make-instance 'permuted-list))
  223.       (initialization-technique ,(make-instance 'random-permutation))
  224.       (operator-list
  225.     ,(list (make-instance 'uniform-order-based-crossover)
  226.            (make-instance 'scramble-sublist-mutation)))
  227.       (operator-weights '(60 40))
  228.       (reproduction-parameterization-techniques
  229.     ,(list (make-instance
  230.          'interpolate-operator-weights
  231.          :interpolation-specs '((70 30) (50 50)))))
  232.       (operator-weights ,(list 70 30))))